题目分析
这个题目可以说是非常经典了,这一系列题目有很多的问法,有路径的长度,有所有路径,有最短路径,有两个方向,有四个方向,有障碍等等,小伙伴们可以进行集中训练。
深度优先搜索
DFS是可以解决这类问题的,但是要进行优化,因为DFS的时间复杂度是指数量级的,因此要进行剪枝。
DFS的剪枝也可以称为记忆化,当搜索过的路径,我们可以将其置为0,在这里因为只要找到一条路径即可,可以直接return true。如果某点无法走到,可以将其置为1,因此就可以在原数据上直接进行操作。在原始数据上,1代表障碍物,这样可以节省开辟visited的内存消耗。
优化后算法的**时间复杂度为$O(mn)$,空间复杂度为$O(mn)$**,其中m和n分别为数据的宽和高。
1 | #include<iostream> |
广度优先搜索
BFS也是可以解决这类问题的,而且在求最短路径时非常好用,但是同样要进行优化,因为BFS的时间复杂度是也是指数量级的,因此要进行剪枝。
BFS和DFS的区别在于,BFS是同时搜索,在求最短路径时非常方便,找到的第一个路径一定是最短路径。而DFS是沿着一条路走到黑,不行再调头,因此在求任意一条路径时非常方便。
BFS的剪枝主要目的是去重,如本题中,(1, 1)这个点,可以由(0, 1)走到,也可以由(1, 0)走到,因此不需要重复计算。如果某点可以已经由其他点走到,可以将其置为1,这里同样可以在原数据上直接进行操作。
算法的**时间复杂度为$O(mn)$,空间复杂度为$O(mn)$**,其中m和n分别为数据的宽和高。
我在这个算法中每一次搜索都保存了所有的路径,因此空间复杂度为$O(mn \cdot max(m, n))$,因为有去重,队列中最多只有max(m, n)条不同的路径。
可以使用哈希表记录最先到达某点的路径,这样可以追溯求出路径,这样只适合于求最短路径,并不是这类问题的通解。如果要求出所有路径,就无法做到了。所有有兴趣的小伙伴可以尝试去做。
1 | #include<iostream> |
动态规划
DP也是可以解决这个问题的,在这里用词要小心,只是这个问题,而不是这类问题,如果移动方向是四个,或者求出所有路径,或者求出最长路径都不方便使用。
我们想一想为什么可以使用动态规划进行求解?因为这个问题具有最优子问题的特点,如走到(5, 5)这个点,可以先走到(4, 5)或者走到(5, 4)这两个点,而这两个点都是已经知道的。因此如果移动方向是4个,那么也可能从(5, 6)或者(6, 5)走到,但是(5, 6)和(6, 5)就说没有求得的,所以不能使用DP。
在求路径的时候,利用回溯的原理,走到(x, y)一定是x + y步,那么如果(x, y - 1)或者(x - 1, y)是x + y - 1,那么就可以从(x, y - 1)或者(x - 1, y)走到(x, y),一直递推到(0, 0)即可。
算法的**时间复杂度为$O(mn)$,空间复杂度为$O(mn)$**,其中m和n分别为数据的宽和高。
1 | #include<iostream> |
刷题总结
这类题目非常重要,面试中考察较少,但是笔试中DFS和BFS是考察的重点,尤其是美团招聘的时候,我记得4道题目都是搜索,这可能和美团的业务相关,需要求各种最短的优化路径。但是考察的难度都很大,如果没有剪枝只能通过30%-40%,而且方法一定要用正确,什么时候该用DFS,什么时候该用BFS,小伙伴们还有很长的路要走,加油吧!